//////////////////////////////////////////////////////////////////////////
///	\file:	Coll.cpp
///	Copyright (MingYou) 2009 - All Rights Reserved
///	Author:	Robert.Ma
///	Date:	[2009/04/27]
///	Description:
///		Copy from Microsoft's MFC, use void* to implement template.
//////////////////////////////////////////////////////////////////////////

#include "StdAfx.h"
#include "Coll.h"

#ifndef SIZE_T_MAX
#define SIZE_T_MAX  UINT_MAX
#endif





/////////////////////////////////////////////////////////////////////////////
// CPlex

void* CPlex::data()
{
	return this + 1;
}

CPlex* PASCAL CPlex::Create(CPlex*& pHead, UINT_PTR nMax, UINT_PTR cbElement)
{
	ASSERT(nMax > 0 && cbElement > 0);
	if (nMax == 0 || cbElement == 0)
	{
		ASSERT(FALSE);
	}

	CPlex* p = (CPlex*) new BYTE[sizeof(CPlex) + nMax * cbElement];
	// may throw exception
	p->pNext = pHead;
	pHead = p;  // change head (adds in reverse order for simplicity)
	return p;
}

void CPlex::FreeDataChain()     // free this one and links
{
	CPlex* p = this;
	while (p != NULL)
	{
		BYTE* bytes = (BYTE*) p;
		CPlex* pTemp = p->pNext;
		delete[] bytes;
		p = pTemp;
	}
}

//////////////////////////////////////////////////////////////////////////
//	CPtrArray

INT_PTR CPtrArray::GetSize() const
{
	return m_nSize;
}

INT_PTR CPtrArray::GetCount() const
{
	return m_nSize;
}

BOOL CPtrArray::IsEmpty() const
{
	return m_nSize == 0;
}

INT_PTR CPtrArray::GetUpperBound() const
{
	return m_nSize -1;
}

void CPtrArray::RemoveAll()
{
	SetSize(0);
}

void* CPtrArray::GetAt(INT_PTR nIndex) const
{
	ASSERT(nIndex >= 0 && nIndex < m_nSize);

	return m_pData[nIndex];
}

void CPtrArray::SetAt(INT_PTR nIndex, void* newElement)
{
	ASSERT(nIndex >= 0 && nIndex < m_nSize);

	m_pData[nIndex] = newElement;
}

void*& CPtrArray::ElementAt(INT_PTR nIndex)
{
	ASSERT(nIndex >= 0 && nIndex < m_nSize);

	return m_pData[nIndex];
}

const void** CPtrArray::GetData() const
{
	return (const void**)m_pData;
}

void** CPtrArray::GetData()
{
	return (void**)m_pData;
}

INT_PTR CPtrArray::Add(void* newElement)
{
	INT_PTR nIndex = m_nSize;
	SetAtGrow(nIndex, newElement);

	return nIndex;
}

void* CPtrArray::operator[](INT_PTR nIndex) const
{
	return GetAt(nIndex);
}

void*& CPtrArray::operator[](INT_PTR nIndex)
{
	return ElementAt(nIndex);
}

CPtrArray::CPtrArray()
{
	m_pData = NULL;
	m_nSize = m_nMaxSize = m_nGrowBy = 0;
}

CPtrArray::~CPtrArray()
{
	ASSERT(this);

	delete[] (BYTE*)m_pData;
}

void CPtrArray::SetSize(INT_PTR nNewSize, INT_PTR nGrowBy)
{
	ASSERT(this);
	ASSERT(nNewSize >= 0);

	if (nGrowBy >= 0)
	{
		m_nGrowBy = nGrowBy;  // set new size
	}

	if (nNewSize == 0)
	{
		// shrink to nothing
		delete[] (BYTE*)m_pData;
		m_pData = NULL;
		m_nSize = m_nMaxSize = 0;
	}
	else if (m_pData == NULL)
	{
		// create one with exact size
#ifdef SIZE_T_MAX
		ASSERT(nNewSize <= SIZE_T_MAX / sizeof(void*));  // no overflow
#endif
		m_pData = (void**) new BYTE[nNewSize * sizeof(void*)];

		memset(m_pData, 0, nNewSize * sizeof(void*));  // zero fill

		m_nSize = m_nMaxSize = nNewSize;
	}
	else if (nNewSize <= m_nMaxSize)
	{
		// it fits
		if (nNewSize > m_nSize)
		{
			// initialize the new elements
			memset(&m_pData[m_nSize], 0, (nNewSize - m_nSize) * sizeof(void*));
		}

		m_nSize = nNewSize;
	}
	else
	{
		// otherwise, grow array
		INT_PTR nGrowArrayBy = m_nGrowBy;
		if (nGrowArrayBy == 0)
		{
			// heuristically determine growth when nGrowArrayBy == 0
			//  (this avoids heap fragmentation in many situations)
			nGrowArrayBy = min(1024, max(4, m_nSize / 8));
		}
		INT_PTR nNewMax;
		if (nNewSize < m_nMaxSize + nGrowArrayBy)
		{
			nNewMax = m_nMaxSize + nGrowArrayBy;  // granularity
		}
		else
		{
			nNewMax = nNewSize;  // no slush
		}

		ASSERT(nNewMax >= m_nMaxSize);  // no wrap around


#ifdef SIZE_T_MAX
		ASSERT(nNewMax <= SIZE_T_MAX / sizeof(void*)); // no overflow
#endif
		void** pNewData = (void**) new BYTE[nNewMax * sizeof(void*)];

		// copy new data from old
		memcpy_s(pNewData, nNewMax * sizeof(void*),
			m_pData, m_nSize * sizeof(void*));

		// construct remaining elements
		ASSERT(nNewSize > m_nSize);

		memset(&pNewData[m_nSize], 0, (nNewSize - m_nSize) * sizeof(void*));

		// get rid of old stuff (note: no destructor called)
		delete[] (BYTE*)m_pData;
		m_pData = pNewData;
		m_nSize = nNewSize;
		m_nMaxSize = nNewMax;
	}
}

INT_PTR CPtrArray::Append(const CPtrArray& src)
{
	ASSERT(this);
	ASSERT(this != &src);   // cannot append to itself

	INT_PTR nOldSize = m_nSize;
	SetSize(m_nSize + src.m_nSize);

	memcpy_s(m_pData + nOldSize, src.m_nSize * sizeof(void*),
		src.m_pData, src.m_nSize * sizeof(void*));

	return nOldSize;
}

void CPtrArray::Copy(const CPtrArray& src)
{
	ASSERT(this);
	ASSERT(this != &src);   // cannot append to itself

	if (this != &src)
	{
		SetSize(src.m_nSize);

		memcpy_s(m_pData, src.m_nSize * sizeof(void*),
			src.m_pData, src.m_nSize * sizeof(void*));
	}

}

void CPtrArray::FreeExtra()
{
	ASSERT(this);

	if (m_nSize != m_nMaxSize)
	{
		// shrink to desired size
#ifdef SIZE_T_MAX
		ASSERT(m_nSize <= SIZE_T_MAX / sizeof(void*)); // no overflow
#endif
		void** pNewData = NULL;
		if (m_nSize != 0)
		{
			pNewData = (void**) new BYTE[m_nSize * sizeof(void*)];

			// copy new data from old
			memcpy_s(pNewData, m_nSize * sizeof(void*),
				m_pData, m_nSize * sizeof(void*));
		}

		// get rid of old stuff (note: no destructors called)
		delete[] (BYTE*)m_pData;
		m_pData = pNewData;
		m_nMaxSize = m_nSize;
	}
}

/////////////////////////////////////////////////////////////////////////////

void CPtrArray::SetAtGrow(INT_PTR nIndex, void* newElement)
{
	ASSERT(this);
	ASSERT(nIndex >= 0);

	if (nIndex >= m_nSize)
	{
		SetSize(nIndex + 1);
	}
	m_pData[nIndex] = newElement;
}

void CPtrArray::InsertAt(INT_PTR nIndex, void* newElement, INT_PTR nCount)
{

	ASSERT(this);
	ASSERT(nIndex >= 0);    // will expand to meet need
	ASSERT(nCount > 0);     // zero or negative size not allowed

	if (nIndex >= m_nSize)
	{
		// adding after the end of the array
		SetSize(nIndex + nCount);  // grow so nIndex is valid
	}
	else
	{
		// inserting in the middle of the array
		INT_PTR nOldSize = m_nSize;
		SetSize(m_nSize + nCount);  // grow it to new size

		// shift old data up to fill gap
		memmove_s(&m_pData[nIndex+nCount], (m_nSize - (nIndex + nCount)) * sizeof(void*),
			&m_pData[nIndex], (nOldSize - nIndex) * sizeof(void*));

		// re-init slots we copied from
		memset(&m_pData[nIndex], 0, nCount * sizeof(void*));
	}

	// insert new value in the gap
	ASSERT(nIndex + nCount <= m_nSize);



	// copy elements into the empty space
	while (nCount--)
	{
		m_pData[nIndex++] = newElement;
	}

}

void CPtrArray::RemoveAt(INT_PTR nIndex, INT_PTR nCount)
{
	ASSERT(this);
	ASSERT(nIndex >= 0);
	ASSERT(nCount >= 0);
	INT_PTR nUpperBound = nIndex + nCount;
	ASSERT(nUpperBound <= m_nSize && nUpperBound >= nIndex && nUpperBound >= nCount);

	// just remove a range
	INT_PTR nMoveCount = m_nSize - (nUpperBound);

	if (nMoveCount)
	{
		memmove_s(&m_pData[nIndex], nMoveCount * sizeof(void*),
			&m_pData[nUpperBound], nMoveCount * sizeof(void*));
	}

	m_nSize -= nCount;
}

void CPtrArray::InsertAt(INT_PTR nStartIndex, CPtrArray* pNewArray)
{
	ASSERT(this);
	ASSERT(pNewArray != NULL);
	ASSERT( NULL != dynamic_cast<CPtrArray*>(pNewArray) );
	ASSERT(pNewArray);
	ASSERT(nStartIndex >= 0);


	if (pNewArray->GetSize() > 0)
	{
		InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize());
		for (INT_PTR i = 0; i < pNewArray->GetSize(); i++)
		{
			SetAt(nStartIndex + i, pNewArray->GetAt(i));
		}
	}
}

//////////////////////////////////////////////////////////////////////////
//	class CPtrList.

INT_PTR CPtrList::GetCount() const
{
	return m_nCount;
}

INT_PTR CPtrList::GetSize() const
{
	return m_nCount;
}

BOOL CPtrList::IsEmpty() const
{
	return m_nCount == 0;
}

void*& CPtrList::GetHead()
{
	ASSERT(m_pNodeHead != NULL);
	return m_pNodeHead->data;
}

const void* CPtrList::GetHead() const
{
	ASSERT(m_pNodeHead != NULL);
	return m_pNodeHead->data;
}

void*& CPtrList::GetTail()
{
	ASSERT(m_pNodeTail != NULL);
	return m_pNodeTail->data;
}

const void* CPtrList::GetTail() const
{
	ASSERT(m_pNodeTail != NULL);
	return m_pNodeTail->data;
}

POSITION CPtrList::GetHeadPosition() const
{
	return (POSITION) m_pNodeHead;
}

POSITION CPtrList::GetTailPosition() const
{
	return (POSITION) m_pNodeTail;
}

void*& CPtrList::GetNext(POSITION& rPosition) // return *Position++
{
	CNode* pNode = (CNode*) rPosition;
	ASSERT( NULL != pNode);

	rPosition = (POSITION) pNode->pNext;
	return pNode->data;
}

const void* CPtrList::GetNext(POSITION& rPosition) const // return *Position++
{
	CNode* pNode = (CNode*) rPosition;
	ASSERT(NULL != pNode);

	rPosition = (POSITION) pNode->pNext;
	return pNode->data;
}

void*& CPtrList::GetPrev(POSITION& rPosition) // return *Position--
{
	CNode* pNode = (CNode*) rPosition;
	ASSERT(NULL != pNode);

	rPosition = (POSITION) pNode->pPrev;
	return pNode->data;
}

const void* CPtrList::GetPrev(POSITION& rPosition) const // return *Position--
{
	CNode* pNode = (CNode*) rPosition;
	ASSERT(NULL != pNode);

	rPosition = (POSITION) pNode->pPrev;
	return pNode->data;
}

void*& CPtrList::GetAt(POSITION position)
{
	CNode* pNode = (CNode*) position;
	ASSERT(NULL != pNode);

	return pNode->data;
}

const void* CPtrList::GetAt(POSITION position) const
{
	CNode* pNode = (CNode*) position;
	ASSERT(NULL != pNode);

	return pNode->data;
}

void CPtrList::SetAt(POSITION pos, void* newElement)
{
	CNode* pNode = (CNode*) pos;
	ASSERT(NULL != pNode);

	pNode->data = newElement;
}

CPtrList::CPtrList(INT_PTR nBlockSize)
{
	ASSERT(nBlockSize > 0);

	m_nCount = 0;
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
	m_pBlocks = NULL;
	m_nBlockSize = nBlockSize;
}

void CPtrList::RemoveAll()
{
	ASSERT(this);

	// destroy elements

	m_nCount = 0;
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks = NULL;
}

CPtrList::~CPtrList()
{
	try
	{
		RemoveAll();
	}
	catch (...)
	{}

	ASSERT(m_nCount == 0);
}

/////////////////////////////////////////////////////////////////////////////
// Node helpers
/*
* Implementation note: CNode's are stored in CPlex blocks and
*  chained together. Free blocks are maintained in a singly linked list
*  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
*  Used blocks are maintained in a doubly linked list using both 'pNext'
*  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
*   as the head/tail.
*
* We never free a CPlex block unless the List is destroyed or RemoveAll()
*  is used - so the total number of CPlex blocks may grow large depending
*  on the maximum past size of the list.
*/

CPtrList::CNode*
CPtrList::NewNode(CPtrList::CNode* pPrev, CPtrList::CNode* pNext)
{
	if (m_pNodeFree == NULL)
	{
		// add another block
		CPlex* pNewBlock = CPlex::Create(m_pBlocks, (UINT)m_nBlockSize,
			sizeof(CNode));

		// chain them into free list
		CNode* pNode = (CNode*) pNewBlock->data();
		// free in reverse order to make it easier to debug
		pNode += m_nBlockSize - 1;
		for (INT_PTR i = m_nBlockSize - 1; i >= 0; i--, pNode--)
		{
			pNode->pNext = m_pNodeFree;
			m_pNodeFree = pNode;
		}
	}
	ASSERT(m_pNodeFree != NULL);  // we must have something

	CPtrList::CNode* pNode = m_pNodeFree;
	m_pNodeFree = m_pNodeFree->pNext;
	pNode->pPrev = pPrev;
	pNode->pNext = pNext;
	m_nCount++;
	ASSERT(m_nCount > 0);  // make sure we don't overflow

	pNode->data = 0; // start with zero

	return pNode;
}

void CPtrList::FreeNode(CPtrList::CNode* pNode)
{
	ASSERT(NULL != pNode);

	pNode->pNext = m_pNodeFree;
	m_pNodeFree = pNode;
	m_nCount--;
	ASSERT(m_nCount >= 0);  // make sure we don't underflow

	// if no more elements, cleanup completely
	if (m_nCount == 0)
	{
		RemoveAll();
	}
}

/////////////////////////////////////////////////////////////////////////////

POSITION CPtrList::AddHead(void* newElement)
{
	ASSERT(this);

	CNode* pNewNode = NewNode(NULL, m_pNodeHead);
	pNewNode->data = newElement;
	if (m_pNodeHead != NULL)
	{
		m_pNodeHead->pPrev = pNewNode;
	}
	else
	{
		m_pNodeTail = pNewNode;
	}
	m_pNodeHead = pNewNode;
	return (POSITION) pNewNode;
}



POSITION CPtrList::AddTail(void* newElement)
{
	ASSERT(this);

	CNode* pNewNode = NewNode(m_pNodeTail, NULL);
	pNewNode->data = newElement;
	if (m_pNodeTail != NULL)
	{
		m_pNodeTail->pNext = pNewNode;
	}
	else
	{
		m_pNodeHead = pNewNode;
	}

	m_pNodeTail = pNewNode;
	return (POSITION) pNewNode;
}

void CPtrList::AddHead(CPtrList* pNewList)
{
	ASSERT(this);
	ASSERT(pNewList);

	// add a list of same elements to head (maintain order)
	POSITION pos = pNewList->GetTailPosition();
	while (pos != NULL)
	{
		AddHead(pNewList->GetPrev(pos));
	}
}

void CPtrList::AddTail(CPtrList* pNewList)
{
	ASSERT(this);
	ASSERT(pNewList);


	// add a list of same elements
	POSITION pos = pNewList->GetHeadPosition();
	while (pos != NULL)
	{
		AddTail(pNewList->GetNext(pos));
	}
}

void* CPtrList::RemoveHead()
{
	ASSERT(this);
	ASSERT(m_pNodeHead != NULL);  // throws if called on empty list


	CNode* pOldNode = m_pNodeHead;
	void* returnValue = pOldNode->data;

	m_pNodeHead = pOldNode->pNext;
	if (m_pNodeHead != NULL)
	{
		m_pNodeHead->pPrev = NULL;
	}
	else
	{
		m_pNodeTail = NULL;
	}
	FreeNode(pOldNode);

	return returnValue;
}

void* CPtrList::RemoveTail()
{
	ASSERT(this);
	ASSERT(m_pNodeTail != NULL);  // don't call on empty list !!!


	CNode* pOldNode = m_pNodeTail;
	void* returnValue = pOldNode->data;

	m_pNodeTail = pOldNode->pPrev;
	if (m_pNodeTail != NULL)
	{
		m_pNodeTail->pNext = NULL;
	}
	else
	{
		m_pNodeHead = NULL;
	}
	FreeNode(pOldNode);
	return returnValue;
}

POSITION CPtrList::InsertBefore(POSITION position, void* newElement)
{
	ASSERT(this);

	if (position == NULL)
	{
		return AddHead(newElement); // insert before nothing -> head of the list
	}

	// Insert it before position
	CNode* pOldNode = (CNode*) position;
	CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
	pNewNode->data = newElement;

	if (pOldNode->pPrev != NULL)
	{
		pOldNode->pPrev->pNext = pNewNode;
	}
	else
	{
		ASSERT(pOldNode == m_pNodeHead);
		m_pNodeHead = pNewNode;
	}
	pOldNode->pPrev = pNewNode;

	return (POSITION) pNewNode;
}



POSITION CPtrList::InsertAfter(POSITION position, void* newElement)
{
	ASSERT(this);

	if (position == NULL)
	{
		return AddTail(newElement); // insert after nothing -> tail of the list
	}

	// Insert it before position
	CNode* pOldNode = (CNode*) position;
	ASSERT( NULL != pOldNode);
	CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
	pNewNode->data = newElement;

	if (pOldNode->pNext != NULL)
	{
		pOldNode->pNext->pPrev = pNewNode;
	}
	else
	{
		ASSERT(pOldNode == m_pNodeTail);
		m_pNodeTail = pNewNode;
	}
	pOldNode->pNext = pNewNode;
	return (POSITION) pNewNode;
}

void CPtrList::RemoveAt(POSITION position)
{
	ASSERT(this);

	CNode* pOldNode = (CNode*) position;
	ASSERT(pOldNode != NULL);

	// remove pOldNode from list
	if (pOldNode == m_pNodeHead)
	{
		m_pNodeHead = pOldNode->pNext;
	}
	else
	{
		pOldNode->pPrev->pNext = pOldNode->pNext;
	}

	if (pOldNode == m_pNodeTail)
	{
		m_pNodeTail = pOldNode->pPrev;
	}
	else
	{
		pOldNode->pNext->pPrev = pOldNode->pPrev;
	}
	FreeNode(pOldNode);
}


/////////////////////////////////////////////////////////////////////////////
// slow operations

POSITION CPtrList::FindIndex(INT_PTR nIndex) const
{
	ASSERT(this);

	if (nIndex >= m_nCount || nIndex < 0)
	{
		return NULL;  // went too far
	}

	CNode* pNode = m_pNodeHead;
	while (nIndex--)
	{
		ASSERT(pNode != NULL);
		pNode = pNode->pNext;
	}
	return (POSITION) pNode;
}

POSITION CPtrList::Find(void* searchValue, POSITION startAfter) const
{
	ASSERT(this);

	CNode* pNode = (CNode*) startAfter;
	if (pNode == NULL)
	{
		pNode = m_pNodeHead;  // start at head
	}
	else
	{
		pNode = pNode->pNext;  // start after the one specified
	}

	for ( ; pNode != NULL; pNode = pNode->pNext )
	{
		if (pNode->data == searchValue)
		{
			return (POSITION) pNode;
		}
	}
	return NULL;
}

//////////////////////////////////////////////////////////////////////////
//	CMapWordToPtr
INT_PTR CMapWordToPtr::GetCount() const
{
	return m_nCount;
}

INT_PTR CMapWordToPtr::GetSize() const
{
	return m_nCount;
}

BOOL CMapWordToPtr::IsEmpty() const
{
	return m_nCount == 0;
}

void CMapWordToPtr::SetAt(WORD key, void* newValue)
{
	(*this)[key] = newValue;
}

POSITION CMapWordToPtr::GetStartPosition() const
{
	return (m_nCount == 0) ? NULL : BEFORE_START_POSITION;
}

UINT CMapWordToPtr::GetHashTableSize() const
{
	return m_nHashTableSize;
}

CMapWordToPtr::CMapWordToPtr(INT_PTR nBlockSize)
{
	ASSERT(nBlockSize > 0);
	if (nBlockSize <= 0)
	{
		nBlockSize = 10;	// default size
	}

	m_pHashTable = NULL;
	m_nHashTableSize = 17;  // default size
	m_nCount = 0;
	m_pFreeList = NULL;
	m_pBlocks = NULL;
	m_nBlockSize = nBlockSize;
}

inline UINT CMapWordToPtr::HashKey(WORD key) const
{
	// default identity hash - works for most primitive values
	return ((DWORD)key) >> 4;
}

void CMapWordToPtr::InitHashTable(UINT nHashSize, BOOL bAllocNow)
//
// Used to force allocation of a hash table or to override the default
//   hash table size of (which is fairly small)
{
	ASSERT(this);
	ASSERT(m_nCount == 0);
	ASSERT(nHashSize > 0);
	if (nHashSize == 0)
	{
		nHashSize = 17;	// default value
	}

	if (m_pHashTable != NULL)
	{
		// free hash table
		delete[] m_pHashTable;
		m_pHashTable = NULL;
	}

	if (bAllocNow)
	{
		m_pHashTable = new CAssoc* [nHashSize];
		memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
	}
	m_nHashTableSize = nHashSize;
}

void CMapWordToPtr::RemoveAll()
{
	ASSERT(this);

	if (m_pHashTable != NULL)
	{
		// free hash table
		delete[] m_pHashTable;
		m_pHashTable = NULL;
	}

	m_nCount = 0;
	m_pFreeList = NULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks = NULL;
}

CMapWordToPtr::~CMapWordToPtr()
{
	try
	{
		RemoveAll();
	}
	catch (...)
	{}
	ASSERT(m_nCount == 0);
}

/////////////////////////////////////////////////////////////////////////////
// Assoc helpers
// same as CList implementation except we store CAssoc's not CNode's
//    and CAssoc's are singly linked all the time
CMapWordToPtr::CAssoc* CMapWordToPtr::NewAssoc()
{
	if (m_pFreeList == NULL)
	{
		// add another block
		CPlex* newBlock = CPlex::Create(m_pBlocks, (UINT)m_nBlockSize, sizeof(CMapWordToPtr::CAssoc));
		// chain them into free list
		CMapWordToPtr::CAssoc* pAssoc = (CMapWordToPtr::CAssoc*) newBlock->data();
		// free in reverse order to make it easier to debug
		pAssoc += m_nBlockSize - 1;
		for (INT_PTR i = m_nBlockSize - 1; i >= 0; i--, pAssoc--)
		{
			pAssoc->pNext = m_pFreeList;
			m_pFreeList = pAssoc;
		}
	}
	ASSERT(m_pFreeList != NULL);  // we must have something

	CMapWordToPtr::CAssoc* pAssoc = m_pFreeList;
	m_pFreeList = m_pFreeList->pNext;
	m_nCount++;
	ASSERT(m_nCount > 0);  // make sure we don't overflow

	pAssoc->key = 0;

	pAssoc->value = 0;

	return pAssoc;
}

void CMapWordToPtr::FreeAssoc(CMapWordToPtr::CAssoc* pAssoc)
{

	pAssoc->pNext = m_pFreeList;
	m_pFreeList = pAssoc;
	m_nCount--;
	ASSERT(m_nCount >= 0);  // make sure we don't underflow

	// if no more elements, cleanup completely
	if (m_nCount == 0)
	{
		RemoveAll();
	}
}

CMapWordToPtr::CAssoc*
CMapWordToPtr::GetAssocAt(WORD key, UINT& nHashBucket, UINT& nHashValue) const
// find association (or return NULL)
{
	nHashValue = HashKey(key);
	nHashBucket = nHashValue % m_nHashTableSize;

	if (m_pHashTable == NULL)
	{
		return NULL;
	}

	// see if it exists
	CAssoc* pAssoc;
	for (pAssoc = m_pHashTable[nHashBucket]; pAssoc != NULL; pAssoc = pAssoc->pNext)
	{
		if (pAssoc->key == key)
		{
			return pAssoc;
		}

	}
	return NULL;
}



/////////////////////////////////////////////////////////////////////////////

BOOL CMapWordToPtr::Lookup(WORD key, void*& rValue) const
{
	ASSERT(this);

	UINT nHashBucket, nHashValue;
	CAssoc* pAssoc = GetAssocAt(key, nHashBucket, nHashValue);
	if (pAssoc == NULL)
	{
		return FALSE;  // not in map
	}

	rValue = pAssoc->value;
	return TRUE;
}

void*& CMapWordToPtr::operator[](WORD key)
{
	ASSERT(this);

	UINT nHashBucket, nHashValue;
	CAssoc* pAssoc;
	if ((pAssoc = GetAssocAt(key, nHashBucket, nHashValue)) == NULL)
	{
		if (m_pHashTable == NULL)
		{
			InitHashTable(m_nHashTableSize);
		}

		// it doesn't exist, add a new Association
		pAssoc = NewAssoc();

		pAssoc->key = key;
		// 'pAssoc->value' is a constructed object, nothing more

		// put into hash table
		pAssoc->pNext = m_pHashTable[nHashBucket];
		m_pHashTable[nHashBucket] = pAssoc;
	}
	return pAssoc->value;  // return new reference
}


BOOL CMapWordToPtr::RemoveKey(WORD key)
// remove key - return TRUE if removed
{
	ASSERT(this);

	if (m_pHashTable == NULL)
	{
		return FALSE;  // nothing in the table
	}

	CAssoc** ppAssocPrev;
	ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];

	CAssoc* pAssoc;
	for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
	{
		if (pAssoc->key == key)
		{
			// remove it
			*ppAssocPrev = pAssoc->pNext;  // remove from list
			FreeAssoc(pAssoc);
			return TRUE;
		}
		ppAssocPrev = &pAssoc->pNext;
	}
	return FALSE;  // not found
}


/////////////////////////////////////////////////////////////////////////////
// Iterating

void CMapWordToPtr::GetNextAssoc(POSITION& rNextPosition,
								 WORD& rKey, void*& rValue) const
{
	ASSERT(this);
	ASSERT(m_pHashTable != NULL);  // never call on empty map

	CAssoc* pAssocRet = (CAssoc*)rNextPosition;
	ASSERT(pAssocRet != NULL);
	if (pAssocRet == NULL)
	{
		return;
	}

	if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
	{
		// find the first association
		for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
		{
			if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
			{
				break;
			}
		}
		ASSERT(pAssocRet != NULL);  // must find something
	}

	// find next association
	ASSERT(NULL != pAssocRet);
	CAssoc* pAssocNext;
	if ((pAssocNext = pAssocRet->pNext) == NULL)
	{
		// go to next bucket

		for (UINT nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1;
			nBucket < m_nHashTableSize; nBucket++)
		{
			if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
			{
				break;
			}
		}
	}

	rNextPosition = (POSITION) pAssocNext;

	// fill in return data
	rKey = pAssocRet->key;
	rValue = pAssocRet->value;
}




//////////////////////////////////////////////////////////////////////////
//	CMapPtrToPtr.
CMapPtrToPtr::CMapPtrToPtr(INT_PTR nBlockSize)
{
	ASSERT(nBlockSize > 0);
	if (nBlockSize <= 0)
	{
		nBlockSize = 10;	// default size
	}

	m_pHashTable = NULL;
	m_nHashTableSize = 17;  // default size
	m_nCount = 0;
	m_pFreeList = NULL;
	m_pBlocks = NULL;
	m_nBlockSize = nBlockSize;
}

inline UINT CMapPtrToPtr::HashKey(void* key) const
{
	// default identity hash - works for most primitive values
	return UINT(DWORD_PTR(key) >> 4);
}

void CMapPtrToPtr::InitHashTable(UINT nHashSize, BOOL bAllocNow)
//
// Used to force allocation of a hash table or to override the default
//   hash table size of (which is fairly small)
{
	ASSERT(this);
	ASSERT(m_nCount == 0);
	ASSERT(nHashSize > 0);
	if ( 0 == nHashSize )
	{
		nHashSize = 17;	// default value
	}

	if (m_pHashTable != NULL)
	{
		// free hash table
		delete[] m_pHashTable;
		m_pHashTable = NULL;
	}

	if (bAllocNow)
	{
		m_pHashTable = new CAssoc* [nHashSize];
		memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
	}
	m_nHashTableSize = nHashSize;
}

void CMapPtrToPtr::RemoveAll()
{
	ASSERT(this);

	if ( NULL != m_pHashTable )
	{
		// free hash table
		delete[] m_pHashTable;
		m_pHashTable = NULL;
	}

	m_nCount	= 0;
	m_pFreeList	= NULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks = NULL;
}

CMapPtrToPtr::~CMapPtrToPtr()
{
	try
	{
		RemoveAll();
	}
	catch (...)
	{}

	ASSERT(m_nCount == 0);
}

/////////////////////////////////////////////////////////////////////////////
// Assoc helpers
// same as CList implementation except we store CAssoc's not CNode's
//    and CAssoc's are singly linked all the time

CMapPtrToPtr::CAssoc*
CMapPtrToPtr::NewAssoc()
{
	if (m_pFreeList == NULL)
	{
		// add another block
		CPlex* newBlock = CPlex::Create(m_pBlocks, (UINT)m_nBlockSize, sizeof(CMapPtrToPtr::CAssoc));
		// chain them into free list
		CMapPtrToPtr::CAssoc* pAssoc = (CMapPtrToPtr::CAssoc*) newBlock->data();
		// free in reverse order to make it easier to debug
		pAssoc += m_nBlockSize - 1;
		for (INT_PTR i = m_nBlockSize - 1; i >= 0; i--, pAssoc--)
		{
			pAssoc->pNext = m_pFreeList;
			m_pFreeList = pAssoc;
		}
	}
	ASSERT(m_pFreeList != NULL);  // we must have something

	CMapPtrToPtr::CAssoc* pAssoc = m_pFreeList;
	m_pFreeList = m_pFreeList->pNext;
	++m_nCount;
	ASSERT(m_nCount > 0);  // make sure we don't overflow

	pAssoc->key = 0;

	pAssoc->value = 0;

	return pAssoc;
}

void CMapPtrToPtr::FreeAssoc(CMapPtrToPtr::CAssoc* pAssoc)
{

	pAssoc->pNext = m_pFreeList;
	m_pFreeList = pAssoc;
	m_nCount--;
	ASSERT(m_nCount >= 0);  // make sure we don't underflow

	// if no more elements, cleanup completely
	if (m_nCount == 0)
		RemoveAll();
}

CMapPtrToPtr::CAssoc*
CMapPtrToPtr::GetAssocAt(void* key, UINT& nHashBucket, UINT& nHashValue) const
// find association (or return NULL)
{
	nHashValue = HashKey(key);
	nHashBucket = nHashValue % m_nHashTableSize;

	if (m_pHashTable == NULL)
		return NULL;

	// see if it exists
	CAssoc* pAssoc;
	for (pAssoc = m_pHashTable[nHashBucket]; pAssoc != NULL; pAssoc = pAssoc->pNext)
	{

		if (pAssoc->key == key)
			return pAssoc;

	}
	return NULL;
}


void* CMapPtrToPtr::GetValueAt(void* key) const
// find value (or return NULL -- NULL values not different as a result)
{
	ASSERT(this);

	if (m_pHashTable == NULL)
		return NULL;

	UINT nHash = HashKey(key) % m_nHashTableSize;

	// see if it exists
	CAssoc* pAssoc;
	for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
	{
		if (pAssoc->key == key)
			return pAssoc->value;
	}
	return NULL;
}


/////////////////////////////////////////////////////////////////////////////

BOOL CMapPtrToPtr::Lookup(void* key, void*& rValue) const
{
	ASSERT(this);

	UINT nHashBucket, nHashValue;
	CAssoc* pAssoc = GetAssocAt(key, nHashBucket, nHashValue);
	if (pAssoc == NULL)
		return FALSE;  // not in map

	rValue = pAssoc->value;
	return TRUE;
}

void*& CMapPtrToPtr::operator[](void* key)
{
	ASSERT(this);

	UINT nHashBucket, nHashValue;
	CAssoc* pAssoc;
	if ((pAssoc = GetAssocAt(key, nHashBucket, nHashValue)) == NULL)
	{
		if (m_pHashTable == NULL)
			InitHashTable(m_nHashTableSize);

		// it doesn't exist, add a new Association
		pAssoc = NewAssoc();

		pAssoc->key = key;
		// 'pAssoc->value' is a constructed object, nothing more

		// put into hash table
		pAssoc->pNext = m_pHashTable[nHashBucket];
		m_pHashTable[nHashBucket] = pAssoc;
	}
	return pAssoc->value;  // return new reference
}


BOOL CMapPtrToPtr::RemoveKey(void* key)
// remove key - return TRUE if removed
{
	ASSERT(this);

	if (m_pHashTable == NULL)
	{
		return FALSE;  // nothing in the table
	}

	CAssoc** ppAssocPrev;
	ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];

	CAssoc* pAssoc;
	for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
	{
		if (pAssoc->key == key)
		{
			// remove it
			*ppAssocPrev = pAssoc->pNext;  // remove from list
			FreeAssoc(pAssoc);
			return TRUE;
		}
		ppAssocPrev = &pAssoc->pNext;
	}
	return FALSE;  // not found
}


/////////////////////////////////////////////////////////////////////////////
// Iterating

void CMapPtrToPtr::GetNextAssoc(POSITION& rNextPosition,
								void*& rKey, void*& rValue) const
{
	ASSERT(this);
	ASSERT(m_pHashTable != NULL);  // never call on empty map

	CAssoc* pAssocRet = (CAssoc*)rNextPosition;
	ASSERT(pAssocRet != NULL);
	if (pAssocRet == NULL)
	{
		return;
	}

	if ( pAssocRet == (CAssoc*) BEFORE_START_POSITION )
	{
		// find the first association
		for ( UINT nBucket = 0; nBucket < m_nHashTableSize; ++nBucket )
		{
			if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
			{
				break;
			}
		}
		ASSERT(pAssocRet != NULL);  // must find something
	}

	// find next association
	ASSERT(NULL != pAssocRet);
	CAssoc* pAssocNext;
	if ((pAssocNext = pAssocRet->pNext) == NULL)
	{
		// go to next bucket

		for (UINT nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1;
			nBucket < m_nHashTableSize; nBucket++)
		{
			if ( (pAssocNext = m_pHashTable[nBucket]) != NULL )
			{
				break;
			}
		}
	}

	rNextPosition = (POSITION) pAssocNext;

	// fill in return data
	rKey = pAssocRet->key;
	rValue = pAssocRet->value;
}

INT_PTR CMapPtrToPtr::GetCount() const
{
	return m_nCount;
}

INT_PTR CMapPtrToPtr::GetSize() const
{
	return m_nCount;
}

BOOL CMapPtrToPtr::IsEmpty() const
{
	return m_nCount == 0;
}

void CMapPtrToPtr::SetAt(void* key, void* newValue)
{
	(*this)[key] = newValue;
}

POSITION CMapPtrToPtr::GetStartPosition() const
{
	return (m_nCount == 0) ? NULL : BEFORE_START_POSITION;
}

UINT CMapPtrToPtr::GetHashTableSize() const
{
	return m_nHashTableSize;
}
